Search for: All records

In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem  $f$is a minimal cover or strong minimal cover of a problem  $h$. We show that strong minimal covers only exist in the cone below  $id$and that the Weihrauch lattice above  $id$is dense. From this, we conclude that the degree of $id$is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic. 

Abstract We consider the Vlasov equation in any spatial dimension, which has long been known [ZI76, Mor80, Gib81, MW82] to be an infinite-dimensional Hamiltonian system whose bracket structure is ofLie–Poisson type. In parallel, it is classical that the Vlasov equation is amean-field limitfor a pairwise interacting Newtonian system. Motivated by this knowledge, we provide a rigorous derivation of the Hamiltonian structure of the Vlasov equation, both the Hamiltonian functional and Poisson bracket, directly from the many-body problem. One may view this work as a classical counterpart to [MNP⁺20], which provided a rigorous derivation of the Hamiltonian structure of the cubic nonlinear Schrödinger equation from the many-body problem for interacting bosons in a certain infinite particle number limit, the first result of its kind. In particular, our work settles a question of Marsden, Morrison and Weinstein [MMW84] on providing a ‘statistical basis’ for the bracket structure of the Vlasov equation. 

Abstract The tower number $${\mathfrak t}$$ and the ultrafilter number $$\mathfrak {u}$$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $$\omega $$ and the almost inclusion relation $$\subseteq ^*$$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $$(G_n)_{n \in {\mathbb N}}$$ of computable sets is a tower if $$G_0 = {\mathbb N}$$ , $$G_{n+1} \subseteq ^* G_n$$ , and $$G_n\smallsetminus G_{n+1}$$ is infinite for each n . A tower is maximal if there is no infinite computable set contained in all $$G_n$$ . A tower $${\left \langle {G_n}\right \rangle }_{n\in \omega }$$ is an ultrafilter base if for each computable R , there is n such that $$G_n \subseteq ^* R$$ or $$G_n \subseteq ^* \overline R$$ ; this property implies maximality of the tower. A sequence $$(G_n)_{n \in {\mathbb N}}$$ of sets can be encoded as the “columns” of a set $$G\subseteq \mathbb N$$ . Our analogs of $${\mathfrak t}$$ and $${\mathfrak u}$$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $$\Delta ^0_2$$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. 

Abstract We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel quotient of the reals reduces to it. 

Abstract Recall that B is PA relative to A if B computes a member of every nonempty $$\Pi ^0_1(A)$$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $$\Pi ^0_1$$ class relative to an enumeration oracle A , which they called a $$\Pi ^0_1{\left \langle {A}\right \rangle }$$ class. We study the induced extension of the relation B is PA relative to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the $${\left \langle {\text {self}\kern1pt}\right \rangle }$$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $$\Pi ^0_1$$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question. 

Abstract The early twenty-first century has witnessed massive expansions in availability and accessibility of digital data in virtually all domains of the biodiversity sciences. Led by an array of asynchronous digitization activities spanning ecological, environmental, climatological, and biological collections data, these initiatives have resulted in a plethora of mostly disconnected and siloed data, leaving to researchers the tedious and time-consuming manual task of finding and connecting them in usable ways, integrating them into coherent data sets, and making them interoperable. The focus to date has been on elevating analog and physical records to digital replicas in local databases prior to elevating them to ever-growing aggregations of essentially disconnected discipline-specific information. In the present article, we propose a new interconnected network of digital objects on the Internet—the Digital Extended Specimen (DES) network—that transcends existing aggregator technology, augments the DES with third-party data through machine algorithms, and provides a platform for more efficient research and robust interdisciplinary discovery.